// 思路： 分为有序和无序两个序列，每轮遍历，将无序序列的第一个元素在有序序列中找到对应的位置插入

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let temp = arr[i]
        let j = i
        while (j > 0 && arr[j - 1] > temp) {
            // 将j-1位置的值向后移动一位
            arr[j] = arr[j - 1]
            j--
        }
        arr[j] = temp
    }
    return arr
}

// 时间复杂度，最好On，最差On^2
// 稳定排序

let arr = [6, 2, 3, 5, 1, 4]
console.log(insertSort(arr))